package 康复训练_JavaGo并驾齐驱;

import java.util.Stack;

public class Jz30包含min函数的栈 {

    /**
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
     * 调用 min、push 及 pop 的时间复杂度都是 O(1)。
     */

    class MinStack {

        // 普通栈
        private Stack<Integer> allStack;
        // 记录最小数
        private Stack<Integer> minStack;

        /** initialize your data structure here. */
        public MinStack() {
            allStack = new Stack<>();
            minStack = new Stack<>();
        }

        public void push(int x) {
            allStack.push(x);
            if (minStack.isEmpty()) {
                minStack.push(x);
                return;
            }
            if (x <= minStack.peek()) {
                minStack.push(x);
            }
        }

        public void pop() {
            Integer num = allStack.pop();
            // 当前最小的元素
            if (num.equals(minStack.peek())) {
                minStack.pop();
            }
        }

        public int top() {
            return allStack.peek();
        }

        public int min() {
            return minStack.peek();
        }
    }

}
